/**
 * @file expansion_graph_instance_ops.h
 * Operations on expantion graph instances
 */

#ifndef EXPANSION_GRAPH_INSTANCE_OPS_H
#define EXPANSION_GRAPH_INSTANCE_OPS_H

#include "expansion_graph_instance.h"

/**
 * Match a vertex to an other vertex in an instance.
 * the other vertex and that the expansions of the first vertex are present on 
 * the other vertex.
 * @param [in] v1 The first vertex to be considered.
 * @param [in] v2 The other vertex to be considered.
 * @param [in] i1 The first instance.
 * @param [in] i2 The other instance.
 * @return @c true if these constraints are satisfied, @c flase otherwise.
 */
template<class V, class E>
  bool match_instance_vertices(V *v1,
                               V *v2, 
                               ExpansionGraphInstance<V, E> *i1,
                               ExpansionGraphInstance<V, E> *i2)
{
  // Check if the vertices themselves match
  if (*v1 == *v2)
    {
      // Get the expansions of the vertices with reference to
      // the instance
      std::map<E*, V*> expansions1, expansions2;
      i1->get_constrained_expansions(v1, &expansions1);
      i2->get_constrained_expansions(v2, &expansions2);
      
      // Iterate over the expansions of the first vertex. Note here
      // that we are going to erase from the map while we iterate
      // through it so we have to increment the iterator in a way 
      // different from a typical 'for' loop. 
      for(typename std::map<E*, V*>::iterator i = expansions1.begin();
          i != expansions1.end();) 
        {
          // Flag to indicate that match has been found
          bool found = false;

          // Iterate over the expansions of the other vertex. Note here
          // that we are going to erase from the map while we iterate
          // through it so we have to increment the iterator in a way 
          // different from a typical 'for' loop. 
          for(typename std::map<E*, V*>::iterator j = expansions2.begin();
              j != expansions2.end();)
            {
              // Check if the expansion matches
              if((*(i->first) == *(j->first)) && (*(i->second) == *(j->second)))
                {
                  // Erase the expansion in the 'other' vertex expansions 
                  expansions2.erase(j++);

                  // Indicate that the match has been found
                  found = true;

                  // We do not need to iterate any further as a match has been
                  // found
                  break;
                }
              else
                j++; // Iterate over the expansions of the other vertex
            }
          
          // Check if a match for the current expansion was found 
          if (found)
            // Erase the expansion in the 'first' vertex expansions
            expansions1.erase(i++); 
          else
            // The current expansion cound not be matched so the vertices
            // cannot match
            return false;         
          }

      // Check if all the expansions have been matched. 
      // Is this really necessary ?
      if (expansions1.empty())
        return true;
      else
        return false;
    }
  // Vertices themselves do not match, no need to consider expansions
  else
    return false;
}

/**
 * Get matching vertices in two instances
 * Given two instances produce and return a many-to-many correspondence
 * between the vertices such that the vertices and their expansions in the first
 * instance are present and identical in the second instance.
 * @param [in] i1 The first instance
 * @param [in] i2 The other instance
 * @param [out] result Result location to write to.
 * @return @c true if all vertices in the first instance have a match in 
 * the other instance, @c false otherwise.
 */
template<class V, class E>
  bool get_instance_vertex_mapping ( ExpansionGraphInstance<V, E> *i1, 
                                     ExpansionGraphInstance<V, E> *i2,
                                     std::multimap<V*, V*> *result )
{
  // Get the vertices of the instances
  std::set<V*> *vertices1, *vertices2;
  i1->get_vertices(&vertices1);
  i2->get_vertices(&vertices2);
    
  // Iterate over the vertices of the first instance
  for(typename std::set<V*>::iterator i = vertices1->begin();
      i != vertices1->end();
      i++)
    {
      // Flag to indicate that match has been found
      bool found = false;

      // Iterate over the vertices of the second instance
      for(typename std::set<V*>::iterator j = vertices2->begin();
          j != vertices2->end();
          j++)
        {
          // Check if the vertices and their expansions are
          // identical
        if(match_instance_vertices(*i,*j, i1, i2))
          {
            // Indicate that a match has been found
            found = true;
            // Add the correspondence to the result multimap
            result->insert(std::pair<V*, V*>(*i,*j));
          }
        }
      // The current vertex from first instance cound not be matched to
      // any vertex from the other instance so a complete correspondence
      // is not possible
      if(! found)
          return false;
    }
  
  // All vertices have atleast one match
  return true;
}

/**
 * Check if two instances are isomorphic for a specific vertex mapping. 
 * Given two instances and a mapping between their vertices check if every 
 * adjacency in the first instance is preserved in the other instance. 
 * @param [in] i1 The first instance.
 * @param [in] i2 The other instance.
 * @param [in] mapping The mapping between vertices to check. 
 * @return @c true if preserved, @c false otherwise.
 */
template<class V, class E>
  bool check_instance_mapping (ExpansionGraphInstance<V, E> *i1, 
                              ExpansionGraphInstance<V, E> *i2, 
                              std::map<V*, V*> *mapping)  
{
  // Iterate over the mapping
  for(typename std::map<V*, V*>::iterator i = mapping->begin();
      i != mapping->end();
      i++)
    {
      // Get the expansions for the current vertex in the first instance
      std::map<E*, V*> *expansions1 = new std::map<E*, V*>;
      
      // Check if it has any expansions
      if(i1->get_constrained_expansions(i->first, expansions1))
        {
          // Iterate over the expansions
          for(typename std::map<E*, V*>::iterator j = expansions1->begin();
              j != expansions1->end();
              j++)
            {
              // Check adjacency for the corresponding vertices in the other 
              // instance. Suppose we are given that vertex A is connected to
              // vertex B through edge C in the first instance and we are given
              // a mapping from A to X and from  C to Z. Then we check if there 
              // exists an edge identical in value to C between X and Z.
              if(! i2->check_adjacency
                 (
                  // Edge
                  j->first, 

                  // Corresponding vertex in the other instance, we use the
                  // 'second' of i as the map is from vertices of i1 to the
                  // vertices of i2
                  i->second, 
                  
                  // Corresponding vertex in the other instance, we have the
                  // vertex in i1 and we use the given mapping to find the
                  // corresponding vertex in i2
                  (mapping->find(j->second))->second 
                  ))
                // Even if a single check fails we can return false
                return false;
            }
        }
      // If there are no expansions, trivially true
      else
        return true;
      
      // Delete the expansions fo the current vertex in the first instance
      delete expansions1;
    }
  // All vertices have identical adjacency 
  return true;
}

#endif // EXPANSION_GRAPH_INSTANCE_OPS_H
